package leetcode

import kotlinetc.println

//https://leetcode.com/problems/valid-parenthesis-string/

/**
Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
An empty string is also valid.
Example 1:
Input: "()"
Output: True
Example 2:
Input: "(*)"
Output: True
Example 3:
Input: "(*))"
Output: True
 */
fun main(args: Array<String>) {

    checkValidString("(*)").println()
}

/**
由于 星号能够通配 空串和左右括号，所以先扫描一遍，确定左右括号的个数，以决定 * 应该匹配什么
 */
fun checkValidString(s: String): Boolean {


    return checkValidString(s, 0, 0, 0)
}

fun checkValidString(s: String, cur: Int, left: Int, right: Int): Boolean {
    if (cur == s.length) {
        return left == right
    }

    if (right > left) return false

    val c = s[cur]
    if (c == '(')
        return checkValidString(s, cur + 1, left + 1, right)

    if (c == ')')
        return checkValidString(s, cur + 1, left, right + 1)

    if (c == '*') {
        if (checkValidString(s, cur + 1, left + 1, right))
            return true
        else if (checkValidString(s, cur + 1, left, right + 1))
            return true
        else return checkValidString(s, cur + 1, left, right)

    }

    return false
}